package com.zfl;

public class IsMatch {

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;
        for (int i = 2; i < n+1; i++) {
            char pChar = p.charAt(i-1);
            if (pChar=='*' && dp[0][i-2]) {
                dp[0][i]=true;
            }
        }

        for (int i = 1; i < m+1; i++) {
            char sChar = s.charAt(i-1);
            for (int j = 1; j < n+1; j++) {
                char pChar = p.charAt(j - 1);

                if (pChar=='.') {
                    dp[i][j]= dp[i-1][j-1];
                } else if(pChar!='*'&&pChar==sChar) {
                    dp[i][j] = dp[i-1][j-1];
                } else if(pChar=='*') {
                    boolean matchZero = dp[i][j - 2];
                    if (matchZero) {
                        dp[i][j]=true;
                        continue;
                    }

                    char pPrev =  p.charAt(j-2);
                    if (pPrev=='.'||pPrev==sChar) {
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }
}
